你绝对想不到，世界上最奇葩的排序算法！

前段时间，分享了《算法导论》中，时间复杂度为O(n)的三种排序：

一个代码极具美感的最美排序：

以及一个只具有分析意义的最慢排序：

然后有水友在评论中留言“是不是下一期要讲睡眠排序了？”。楼主才疏学浅，没有听过“睡眠排序”，网上搜了一下，眼界大开。

这是一个不但没有工程意义，也不具有分析意义，甚至未必能得到正确的排序结果的排序。既然大伙充满好奇心，那就简单分享一下。

话不多说，先上伪代码：

void sleep_sort(uint arr[], uint n){

        for(uint i=0;i<n;i++){

                Thread t = new Thread(){

                         @Override

                         public void run(){

                                  sleep(arr[i]);

                                  print(arr[i]);

                         }

                };

                t.start();

        }

}

看了伪代码，很容易理解其核心思路是：

（1）循环遍历待排序数组中的每一个元素x；

（2）启动一个新线程，睡眠x毫秒，然后输出x；

算法认为：

（1）小的元素xi，睡眠时间少，会先输出；

（2）大的元素xj，睡眠时间长，会后输出；

看完算法，请不要提出如下疑问：

（1）如果元素是负数怎么办？

（2）如果元素很接近怎么办？

（3）为什么没有考虑线程调度时间？

（4）如果线程太多，CPU调度不过来怎么办？

（5）…

《世界上最慢的排序算法！》尚有时间复杂度分析的意义，睡眠算法似乎完全没有什么luan用。哎，如果认真，我们就输了。

能够想出这个算法的童鞋，你真是个天才。

调研：

你还见过更奇葩的排序算法吗？

时间复杂度为O(n)的三种排序：

另外：

你知道睡眠排序的时间复杂度是多少吗？